SherbyNet - /page/wikibook/entry.mu

<!DOCTYPE html>

<title>Revised simplex method</title>

</head>

<span id="openzim-page-title" class="mw-page-title-main"><span class="mw-page-title-main">Revised simplex method</span></span>

</h1>

</header>

<div id="mw-content-text" class="mw-body-content mw-content-ltr" lang="en" dir="ltr"><div class="mw-content-ltr mw-parser-output" lang="en" dir="ltr"><p>In <a href="Mathematical_optimization" title="Mathematical optimization">mathematical optimization</a>, the <b>revised simplex method</b> is a variant of <a href="George_Dantzig" title="George Dantzig">George Dantzig</a>'s <a href="Simplex_method" class="mw-redirect" title="Simplex method">simplex method</a> for <a href="Linear_programming" title="Linear programming">linear programming</a>.

</p><p>The revised simplex method is mathematically equivalent to the standard simplex method but differs in implementation. Instead of maintaining a tableau which explicitly represents the constraints adjusted to a set of basic variables, it maintains a representation of a <a href="Basis_(linear_algebra)" title="Basis (linear algebra)">basis</a> of the <a href="Matrix_(mathematics)" title="Matrix (mathematics)">matrix</a> representing the constraints. The matrix-oriented approach allows for greater computational efficiency by enabling sparse matrix operations.<sup id="cite_ref-FOOTNOTEMorgan1997§2_1-0" class="reference"><a href="#cite_note-FOOTNOTEMorgan1997§2-1"><span class="cite-bracket">[</span>1<span class="cite-bracket">]</span></a></sup>

</p>

<div class="mw-heading mw-heading2"><h2 id="Problem_formulation">Problem formulation</h2></div>

<p>For the rest of the discussion, it is assumed that a linear programming problem has been converted into the following standard form:

</p>

<mtr>

<mtd>

<mtext>minimize</mtext>

</mrow>

</mtd>

<mtd>

<msup>

</mrow>

</mrow>

</msup>

</mrow>

</mtd>

</mtr>

<mtr>

<mtd>

<mtext>subject to</mtext>

</mrow>

</mtd>

<mtd>

</mrow>

</mrow>

</mrow>

</mrow>

</mtd>

</mtr>

</mtable>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle {\begin{array}{rl}{\text{minimize}}&{\boldsymbol {c}}^{\mathrm {T} }{\boldsymbol {x}}\\{\text{subject to}}&{\boldsymbol {Ax}}={\boldsymbol {b}},{\boldsymbol {x}}\geq {\boldsymbol {0}}\end{array}}}</annotation>

</semantics>

</math></span><img src="./7ac0433efdd5048279e5e39ee0671c071d81ba9f.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -2.263ex; margin-bottom: -0.242ex; width:27.766ex; height:6.176ex;" alt="{\displaystyle {\begin{array}{rl}{\text{minimize}}&{\boldsymbol {c}}^{\mathrm {T} }{\boldsymbol {x}}\\{\text{subject to}}&{\boldsymbol {Ax}}={\boldsymbol {b}},{\boldsymbol {x}}\geq {\boldsymbol {0}}\end{array}}}" loading="lazy"></span></dd></dl>

<p>where <span class="texhtml"><i><b>A</b></i> ∈ ℝ<sup><i>m</i>×<i>n</i></sup></span>. Without loss of generality, it is assumed that the constraint matrix <span class="texhtml"><i><b>A</b></i></span> has full row rank and that the problem is feasible, i.e., there is at least one <span class="texhtml"><i><b>x</b></i> ≥ <b>0</b></span> such that <span class="texhtml"><i><b>Ax</b></i> = <i><b>b</b></i></span>. If <span class="texhtml"><i><b>A</b></i></span> is rank-deficient, either there are redundant constraints, or the problem is infeasible. Both situations can be handled by a presolve step.

</p>

<div class="mw-heading mw-heading2"><h2 id="Algorithmic_description">Algorithmic description</h2></div>

<div class="mw-heading mw-heading3"><h3 id="Optimality_conditions">Optimality conditions</h3></div>

<p>For linear programming, the <a href="Karush%E2%80%93Kuhn%E2%80%93Tucker_conditions" title="Karush–Kuhn–Tucker conditions">Karush–Kuhn–Tucker conditions</a> are both <a href="Necessary_and_sufficient" class="mw-redirect" title="Necessary and sufficient">necessary and sufficient</a> for optimality. The KKT conditions of a linear programming problem in the standard form is

</p>

<mtr>

<mtd>

</mrow>

</mtd>

<mtd>

</mrow>

</mtd>

</mtr>

<mtr>

<mtd>

<msup>

</mrow>

</mrow>

</msup>

</mrow>

</mrow>

</mtd>

<mtd>

</mrow>

</mtd>

</mtr>

<mtr>

<mtd>

</mrow>

</mtd>

<mtd>

</mrow>

</mtd>

</mtr>

<mtr>

<mtd>

</mrow>

</mtd>

<mtd>

</mrow>

</mtd>

</mtr>

<mtr>

<mtd>

<msup>

</mrow>

</mrow>

</msup>

</mrow>

</mtd>

<mtd>

</mtd>

</mtr>

</mtable>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle {\begin{aligned}{\boldsymbol {Ax}}&={\boldsymbol {b}},\\{\boldsymbol {A}}^{\mathrm {T} }{\boldsymbol {\lambda }}+{\boldsymbol {s}}&={\boldsymbol {c}},\\{\boldsymbol {x}}&\geq {\boldsymbol {0}},\\{\boldsymbol {s}}&\geq {\boldsymbol {0}},\\{\boldsymbol {s}}^{\mathrm {T} }{\boldsymbol {x}}&=0\end{aligned}}}</annotation>

</semantics>

</math></span><img src="./792554b32d918b8062ae809e014623e1ae43d73c.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -7.171ex; width:14.906ex; height:15.509ex;" alt="{\displaystyle {\begin{aligned}{\boldsymbol {Ax}}&={\boldsymbol {b}},\\{\boldsymbol {A}}^{\mathrm {T} }{\boldsymbol {\lambda }}+{\boldsymbol {s}}&={\boldsymbol {c}},\\{\boldsymbol {x}}&\geq {\boldsymbol {0}},\\{\boldsymbol {s}}&\geq {\boldsymbol {0}},\\{\boldsymbol {s}}^{\mathrm {T} }{\boldsymbol {x}}&=0\end{aligned}}}" loading="lazy"></span></dd></dl>

<p>where <span class="texhtml"><i><b>λ</b></i></span> and <span class="texhtml"><i><b>s</b></i></span> are the <a href="Lagrange_multiplier" title="Lagrange multiplier">Lagrange multipliers</a> associated with the constraints <span class="texhtml"><i><b>Ax</b></i> = <i><b>b</b></i></span> and <span class="texhtml"><i><b>x</b></i> ≥ <b>0</b></span>, respectively.<sup id="cite_ref-FOOTNOTENocedalWright2006358Eq.&nbsp;13.4_2-0" class="reference"><a href="#cite_note-FOOTNOTENocedalWright2006358Eq.&nbsp;13.4-2"><span class="cite-bracket">[</span>2<span class="cite-bracket">]</span></a></sup> The last condition, which is equivalent to <span class="texhtml"><i>s<sub>i</sub>x<sub>i</sub></i> = 0</span> for all <span class="texhtml">1 < <i>i</i> < <i>n</i></span>, is called the <i>complementary slackness condition</i>.

</p><p>By what is sometimes known as the <i>fundamental theorem of linear programming</i>, a vertex <span class="texhtml"><i><b>x</b></i></span> of the feasible polytope can be identified by being a basis <span class="texhtml"><i><b>B</b></i></span> of <span class="texhtml"><i><b>A</b></i></span> chosen from the latter's columns.<sup id="cite_ref-4" class="reference"><a href="#cite_note-4"><span class="cite-bracket">[</span>a<span class="cite-bracket">]</span></a></sup> Since <span class="texhtml"><i><b>A</b></i></span> has full rank, <span class="texhtml"><i><b>B</b></i></span> is nonsingular. Without loss of generality, assume that <span class="texhtml"><i><b>A</b></i> = [<i><b>B</b></i> <i><b>N</b></i>]</span>. Then <span class="texhtml"><i><b>x</b></i></span> is given by

</p>

</mrow>

<mrow>

<mtr>

<mtd>

<msub>

</mrow>

</msub>

</mrow>

</mtd>

</mtr>

<mtr>

<mtd>

<msub>

</mrow>

</msub>

</mrow>

</mtd>

</mtr>

</mtable>

</mrow>

<mrow>

<mtr>

<mtd>

<msup>

</mrow>

</mrow>

</msup>

</mrow>

</mtd>

</mtr>

<mtr>

<mtd>

</mrow>

</mtd>

</mtr>

</mtable>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle {\boldsymbol {x}}={\begin{bmatrix}{\boldsymbol {x_{B}}}\\{\boldsymbol {x_{N}}}\end{bmatrix}}={\begin{bmatrix}{\boldsymbol {B}}^{-1}{\boldsymbol {b}}\\{\boldsymbol {0}}\end{bmatrix}}}</annotation>

</semantics>

</math></span><img src="./348f7237784588fd41711762217b6a3ff80807bf.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -2.505ex; width:23.15ex; height:6.176ex;" alt="{\displaystyle {\boldsymbol {x}}={\begin{bmatrix}{\boldsymbol {x_{B}}}\\{\boldsymbol {x_{N}}}\end{bmatrix}}={\begin{bmatrix}{\boldsymbol {B}}^{-1}{\boldsymbol {b}}\\{\boldsymbol {0}}\end{bmatrix}}}" loading="lazy"></span></dd></dl>

<p>where <span class="texhtml"><i><b>x<sub>B</sub></b></i> ≥ <b>0</b></span>. Partition <span class="texhtml"><i><b>c</b></i></span> and <span class="texhtml"><i><b>s</b></i></span> accordingly into

</p>

<mtr>

<mtd>

</mrow>

</mtd>

<mtd>

<mrow>

<mtr>

<mtd>

<msub>

</mrow>

</msub>

</mrow>

</mtd>

</mtr>

<mtr>

<mtd>

<msub>

</mrow>

</msub>

</mrow>

</mtd>

</mtr>

</mtable>

</mrow>

</mtd>

</mtr>

<mtr>

<mtd>

</mrow>

</mtd>

<mtd>

<mrow>

<mtr>

<mtd>

<msub>

</mrow>

</msub>

</mrow>

</mtd>

</mtr>

<mtr>

<mtd>

<msub>

</mrow>

</msub>

</mrow>

</mtd>

</mtr>

</mtable>

</mrow>

</mtd>

</mtr>

</mtable>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle {\begin{aligned}{\boldsymbol {c}}&={\begin{bmatrix}{\boldsymbol {c_{B}}}\\{\boldsymbol {c_{N}}}\end{bmatrix}},\\{\boldsymbol {s}}&={\begin{bmatrix}{\boldsymbol {s_{B}}}\\{\boldsymbol {s_{N}}}\end{bmatrix}}.\end{aligned}}}</annotation>

</semantics>

</math></span><img src="./4c8e5b6b393b758a28904153e4f516e690cf3e27.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -5.671ex; width:12.092ex; height:12.509ex;" alt="{\displaystyle {\begin{aligned}{\boldsymbol {c}}&={\begin{bmatrix}{\boldsymbol {c_{B}}}\\{\boldsymbol {c_{N}}}\end{bmatrix}},\\{\boldsymbol {s}}&={\begin{bmatrix}{\boldsymbol {s_{B}}}\\{\boldsymbol {s_{N}}}\end{bmatrix}}.\end{aligned}}}" loading="lazy"></span></dd></dl>

<p>To satisfy the complementary slackness condition, let <span class="texhtml"><i><b>s<sub>B</sub></b></i> = <b>0</b></span>. It follows that

</p>

<mtr>

<mtd>

<msup>

</mrow>

</mrow>

</msup>

</mrow>

</mtd>

<mtd>

<msub>

</mrow>

</msub>

</mrow>

</mtd>

</mtr>

<mtr>

<mtd>

<msup>

</mrow>

</mrow>

</msup>

</mrow>

<msub>

</mrow>

</msub>

</mrow>

</mtd>

<mtd>

<msub>

</mrow>

</msub>

</mrow>

</mtd>

</mtr>

</mtable>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle {\begin{aligned}{\boldsymbol {B}}^{\mathrm {T} }{\boldsymbol {\lambda }}&={\boldsymbol {c_{B}}},\\{\boldsymbol {N}}^{\mathrm {T} }{\boldsymbol {\lambda }}+{\boldsymbol {s_{N}}}&={\boldsymbol {c_{N}}},\end{aligned}}}</annotation>

</semantics>

</math></span><img src="./aab468abfc5db7f6e5c026cc1a250e98ebc58126.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -2.505ex; width:19.022ex; height:6.176ex;" alt="{\displaystyle {\begin{aligned}{\boldsymbol {B}}^{\mathrm {T} }{\boldsymbol {\lambda }}&={\boldsymbol {c_{B}}},\\{\boldsymbol {N}}^{\mathrm {T} }{\boldsymbol {\lambda }}+{\boldsymbol {s_{N}}}&={\boldsymbol {c_{N}}},\end{aligned}}}" loading="lazy"></span></dd></dl>

<p>which implies that

</p>

<mtr>

<mtd>

</mrow>

</mtd>

<mtd>

<msup>

</mrow>

</mrow>

</msup>

<msup>

</mrow>

</msup>

<msub>

</mrow>

</msub>

</mrow>

</mtd>

</mtr>

<mtr>

<mtd>

<msub>

</mrow>

</msub>

</mrow>

</mtd>

<mtd>

<msub>

</mrow>

</msub>

</mrow>

<msup>

</mrow>

</mrow>

</msup>

</mrow>

</mtd>

</mtr>

</mtable>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle {\begin{aligned}{\boldsymbol {\lambda }}&=({\boldsymbol {B}}^{\mathrm {T} })^{-1}{\boldsymbol {c_{B}}},\\{\boldsymbol {s_{N}}}&={\boldsymbol {c_{N}}}-{\boldsymbol {N}}^{\mathrm {T} }{\boldsymbol {\lambda }}.\end{aligned}}}</annotation>

</semantics>

</math></span><img src="./351c02672b3a97b611bd69af93b1c2bb8380fea0.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -2.671ex; width:19.022ex; height:6.509ex;" alt="{\displaystyle {\begin{aligned}{\boldsymbol {\lambda }}&=({\boldsymbol {B}}^{\mathrm {T} })^{-1}{\boldsymbol {c_{B}}},\\{\boldsymbol {s_{N}}}&={\boldsymbol {c_{N}}}-{\boldsymbol {N}}^{\mathrm {T} }{\boldsymbol {\lambda }}.\end{aligned}}}" loading="lazy"></span></dd></dl>

<p>If <span class="texhtml"><i><b>s<sub>N</sub></b></i> ≥ <b>0</b></span> at this point, the KKT conditions are satisfied, and thus <span class="texhtml"><i><b>x</b></i></span> is optimal.

</p>

<div class="mw-heading mw-heading3"><h3 id="Pivot_operation">Pivot operation</h3></div>

<p>If the KKT conditions are violated, a <i>pivot operation</i> consisting of introducing a column of <span class="texhtml"><i><b>N</b></i></span> into the basis at the expense of an existing column in <span class="texhtml"><i><b>B</b></i></span> is performed. In the absence of <a href="Degeneracy_(mathematics)" title="Degeneracy (mathematics)">degeneracy</a>, a pivot operation always results in a strict decrease in <span class="texhtml"><i><b>c</b></i><sup>T</sup><i><b>x</b></i></span>. Therefore, if the problem is bounded, the revised simplex method must terminate at an optimal vertex after repeated pivot operations because there are only a finite number of vertices.<sup id="cite_ref-FOOTNOTENocedalWright2006370Theorem&nbsp;13.4_5-0" class="reference"><a href="#cite_note-FOOTNOTENocedalWright2006370Theorem&nbsp;13.4-5"><span class="cite-bracket">[</span>4<span class="cite-bracket">]</span></a></sup>

</p><p>Select an index <span class="texhtml"><i>m</i> < <i>q</i> ≤ <i>n</i></span> such that <span class="texhtml"><i>s<sub>q</sub></i> < 0</span> as the <i>entering index</i>. The corresponding column of <span class="texhtml"><i><b>A</b></i></span>, <span class="texhtml"><i><b>A</b><sub>q</sub></i></span>, will be moved into the basis, and <span class="texhtml"><i>x<sub>q</sub></i></span> will be allowed to increase from zero. It can be shown that

</p>

<mfrac>

<mrow>

<msup>

</mrow>

</mrow>

</msup>

</mrow>

</mrow>

<mrow>

<msub>

</mrow>

</msub>

</mrow>

</mfrac>

</mrow>

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle {\frac {\partial ({\boldsymbol {c}}^{\mathrm {T} }{\boldsymbol {x}})}{\partial x_{q}}}=s_{q},}</annotation>

</semantics>

</math></span><img src="./4ff370c40236c1a326a31d166c5a102da0766e8f.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -2.671ex; width:13.931ex; height:6.676ex;" alt="{\displaystyle {\frac {\partial ({\boldsymbol {c}}^{\mathrm {T} }{\boldsymbol {x}})}{\partial x_{q}}}=s_{q},}" loading="lazy"></span></dd></dl>

<p>i.e., every unit increase in <span class="texhtml"><i>x<sub>q</sub></i></span> results in a decrease by <span class="texhtml">−<i>s<sub>q</sub></i></span> in <span class="texhtml"><i><b>c</b></i><sup>T</sup><i><b>x</b></i></span>.<sup id="cite_ref-FOOTNOTENocedalWright2006369Eq.&nbsp;13.24_6-0" class="reference"><a href="#cite_note-FOOTNOTENocedalWright2006369Eq.&nbsp;13.24-6"><span class="cite-bracket">[</span>5<span class="cite-bracket">]</span></a></sup> Since

</p>

<msub>

</mrow>

</msub>

</mrow>

<msub>

</mrow>

</mrow>

</msub>

<msub>

</mrow>

</msub>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle {\boldsymbol {Bx_{B}}}+{\boldsymbol {A}}_{q}x_{q}={\boldsymbol {b}},}</annotation>

</semantics>

</math></span><img src="./f9c96a14bb072ce61848e6bb44a0b7e198bc603a.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -1.005ex; width:18.323ex; height:2.843ex;" alt="{\displaystyle {\boldsymbol {Bx_{B}}}+{\boldsymbol {A}}_{q}x_{q}={\boldsymbol {b}},}" loading="lazy"></span></dd></dl>

<p><span class="texhtml"><i><b>x<sub>B</sub></b></i></span> must be correspondingly decreased by <span class="texhtml">Δ<i><b>x<sub>B</sub></b></i> = <i><b>B</b></i><sup>−1</sup><i><b>A</b><sub>q</sub>x<sub>q</sub></i></span> subject to <span class="texhtml"><i><b>x<sub>B</sub></b></i> − Δ<i><b>x<sub>B</sub></b></i> ≥ <b>0</b></span>. Let <span class="texhtml"><i><b>d</b></i> = <i><b>B</b></i><sup>−1</sup><i><b>A</b><sub>q</sub></i></span>. If <span class="texhtml"><i><b>d</b></i> ≤ <b>0</b></span>, no matter how much <span class="texhtml"><i>x<sub>q</sub></i></span> is increased, <span class="texhtml"><i><b>x<sub>B</sub></b></i> − Δ<i><b>x<sub>B</sub></b></i></span> will stay nonnegative. Hence, <span class="texhtml"><i><b>c</b></i><sup>T</sup><i><b>x</b></i></span> can be arbitrarily decreased, and thus the problem is unbounded. Otherwise, select an index <span class="texhtml"><i>p</i> = argmin<sub>1≤<i>i</i>≤<i>m</i></sub> {<i>x<sub>i</sub></i>/<i>d<sub>i</sub></i> | <i>d<sub>i</sub></i> > 0}</span> as the <i>leaving index</i>. This choice effectively increases <span class="texhtml"><i>x<sub>q</sub></i></span> from zero until <span class="texhtml"><i>x<sub>p</sub></i></span> is reduced to zero while maintaining feasibility. The pivot operation concludes with replacing <span class="texhtml"><i><b>A</b><sub>p</sub></i></span> with <span class="texhtml"><i><b>A</b><sub>q</sub></i></span> in the basis.

</p>

<div class="mw-heading mw-heading2"><h2 id="Numerical_example">Numerical example</h2></div>

/* start https://en.wikipedia.org/ */

.mw-parser-output .hatnote{font-style:italic}.mw-parser-output div.hatnote{padding-left:1.6em;margin-bottom:0.5em}.mw-parser-output .hatnote i{font-style:normal}.mw-parser-output .hatnote+link+.hatnote{margin-top:-0.5em}@media print{body.ns-0 .mw-parser-output .hatnote{display:none!important}}

/* end https://en.wikipedia.org/ */

</style><div role="note" class="hatnote navigation-not-searchable">See also: <a href="Simplex_method" class="mw-redirect" title="Simplex method">Simplex method § Example</a></div>

<p>Consider a linear program where

</p>

<mtr>

<mtd>

</mrow>

</mtd>

<mtd>

<msup>

<mrow>

<mtr>

<mtd>

</mtd>

<mtd>

</mtd>

<mtd>

</mtd>

<mtd>

</mtd>

<mtd>

</mtd>

</mtr>

</mtable>

</mrow>

</mrow>

</msup>

</mtd>

</mtr>

<mtr>

<mtd>

</mrow>

</mtd>

<mtd>

<mrow>

<mtr>

<mtd>

</mtd>

<mtd>

</mtd>

<mtd>

</mtd>

<mtd>

</mtd>

<mtd>

</mtd>

</mtr>

<mtr>

<mtd>

</mtd>

<mtd>

</mtd>

<mtd>

</mtd>

<mtd>

</mtd>

<mtd>

</mtd>

</mtr>

</mtable>

</mrow>

</mtd>

</mtr>

<mtr>

<mtd>

</mrow>

</mtd>

<mtd>

<mrow>

<mtr>

<mtd>

</mtd>

</mtr>

<mtr>

<mtd>

</mtd>

</mtr>

</mtable>

</mrow>

</mtd>

</mtr>

</mtable>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle {\begin{aligned}{\boldsymbol {c}}&={\begin{bmatrix}-2&-3&-4&0&0\end{bmatrix}}^{\mathrm {T} },\\{\boldsymbol {A}}&={\begin{bmatrix}3&2&1&1&0\\2&5&3&0&1\end{bmatrix}},\\{\boldsymbol {b}}&={\begin{bmatrix}10\\15\end{bmatrix}}.\end{aligned}}}</annotation>

</semantics>

</math></span><img src="./0315a7ea7488009d14be407b4c8fcbfc8eb8cbc0.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -7.338ex; width:30.507ex; height:15.843ex;" alt="{\displaystyle {\begin{aligned}{\boldsymbol {c}}&={\begin{bmatrix}-2&-3&-4&0&0\end{bmatrix}}^{\mathrm {T} },\\{\boldsymbol {A}}&={\begin{bmatrix}3&2&1&1&0\\2&5&3&0&1\end{bmatrix}},\\{\boldsymbol {b}}&={\begin{bmatrix}10\\15\end{bmatrix}}.\end{aligned}}}" loading="lazy"></span></dd></dl>

<p>Let

</p>

<mtr>

<mtd>

</mrow>

</mtd>

<mtd>

<mrow>

<mtr>

<mtd>

<msub>

</mrow>

</mrow>

</msub>

</mtd>

<mtd>

<msub>

</mrow>

</mrow>

</msub>

</mtd>

</mtr>

</mtable>

</mrow>

</mtd>

</mtr>

<mtr>

<mtd>

</mrow>

</mtd>

<mtd>

<mrow>

<mtr>

<mtd>

<msub>

</mrow>

</mrow>

</msub>

</mtd>

<mtd>

<msub>

</mrow>

</mrow>

</msub>

</mtd>

<mtd>

<msub>

</mrow>

</mrow>

</msub>

</mtd>

</mtr>

</mtable>

</mrow>

</mtd>

</mtr>

</mtable>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle {\begin{aligned}{\boldsymbol {B}}&={\begin{bmatrix}{\boldsymbol {A}}_{4}&{\boldsymbol {A}}_{5}\end{bmatrix}},\\{\boldsymbol {N}}&={\begin{bmatrix}{\boldsymbol {A}}_{1}&{\boldsymbol {A}}_{2}&{\boldsymbol {A}}_{3}\end{bmatrix}}\end{aligned}}}</annotation>

</semantics>

</math></span><img src="./571d52f568918bc43f7d0f280ec694d3e3d2a9fe.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -2.505ex; width:22.148ex; height:6.176ex;" alt="{\displaystyle {\begin{aligned}{\boldsymbol {B}}&={\begin{bmatrix}{\boldsymbol {A}}_{4}&{\boldsymbol {A}}_{5}\end{bmatrix}},\\{\boldsymbol {N}}&={\begin{bmatrix}{\boldsymbol {A}}_{1}&{\boldsymbol {A}}_{2}&{\boldsymbol {A}}_{3}\end{bmatrix}}\end{aligned}}}" loading="lazy"></span></dd></dl>

<p>initially, which corresponds to a feasible vertex <span class="texhtml"><i><b>x</b></i> = [0 0 0 10 15]<sup>T</sup></span>. At this moment,

</p>

<mtr>

<mtd>

</mrow>

</mtd>

<mtd>

<msup>

<mrow>

<mtr>

<mtd>

</mtd>

<mtd>

</mtd>

</mtr>

</mtable>

</mrow>

</mrow>

</msup>

</mtd>

</mtr>

<mtr>

<mtd>

<msub>

</mrow>

</msub>

</mrow>

</mtd>

<mtd>

<msup>

<mrow>

<mtr>

<mtd>

</mtd>

<mtd>

</mtd>

<mtd>

</mtd>

</mtr>

</mtable>

</mrow>

</mrow>

</msup>

</mtd>

</mtr>

</mtable>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle {\begin{aligned}{\boldsymbol {\lambda }}&={\begin{bmatrix}0&0\end{bmatrix}}^{\mathrm {T} },\\{\boldsymbol {s_{N}}}&={\begin{bmatrix}-2&-3&-4\end{bmatrix}}^{\mathrm {T} }.\end{aligned}}}</annotation>

</semantics>

</math></span><img src="./8ab29742cc5dff65d315159de2326053e77dcc85.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -2.838ex; width:24.672ex; height:6.843ex;" alt="{\displaystyle {\begin{aligned}{\boldsymbol {\lambda }}&={\begin{bmatrix}0&0\end{bmatrix}}^{\mathrm {T} },\\{\boldsymbol {s_{N}}}&={\begin{bmatrix}-2&-3&-4\end{bmatrix}}^{\mathrm {T} }.\end{aligned}}}" loading="lazy"></span></dd></dl>

<p>Choose <span class="texhtml"><i>q</i> = 3</span> as the entering index. Then <span class="texhtml"><i><b>d</b></i> = [1 3]<sup>T</sup></span>, which means a unit increase in <span class="texhtml"><i>x</i><sub>3</sub></span> results in <span class="texhtml"><i>x</i><sub>4</sub></span> and <span class="texhtml"><i>x</i><sub>5</sub></span> being decreased by <span class="texhtml">1</span> and <span class="texhtml">3</span>, respectively. Therefore, <span class="texhtml"><i>x</i><sub>3</sub></span> is increased to <span class="texhtml">5</span>, at which point <span class="texhtml"><i>x</i><sub>5</sub></span> is reduced to zero, and <span class="texhtml"><i>p</i> = 5</span> becomes the leaving index.

</p><p>After the pivot operation,

</p>

<mtr>

<mtd>

</mrow>

</mtd>

<mtd>

<mrow>

<mtr>

<mtd>

<msub>

</mrow>

</mrow>

</msub>

</mtd>

<mtd>

<msub>

</mrow>

</mrow>

</msub>

</mtd>

</mtr>

</mtable>

</mrow>

</mtd>

</mtr>

<mtr>

<mtd>

</mrow>

</mtd>

<mtd>

<mrow>

<mtr>

<mtd>

<msub>

</mrow>

</mrow>

</msub>

</mtd>

<mtd>

<msub>

</mrow>

</mrow>

</msub>

</mtd>

<mtd>

<msub>

</mrow>

</mrow>

</msub>

</mtd>

</mtr>

</mtable>

</mrow>

</mtd>

</mtr>

</mtable>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle {\begin{aligned}{\boldsymbol {B}}&={\begin{bmatrix}{\boldsymbol {A}}_{3}&{\boldsymbol {A}}_{4}\end{bmatrix}},\\{\boldsymbol {N}}&={\begin{bmatrix}{\boldsymbol {A}}_{1}&{\boldsymbol {A}}_{2}&{\boldsymbol {A}}_{5}\end{bmatrix}}.\end{aligned}}}</annotation>

</semantics>

</math></span><img src="./17710584d5fbd788abc33e5231a194e28865631e.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -2.505ex; width:22.795ex; height:6.176ex;" alt="{\displaystyle {\begin{aligned}{\boldsymbol {B}}&={\begin{bmatrix}{\boldsymbol {A}}_{3}&{\boldsymbol {A}}_{4}\end{bmatrix}},\\{\boldsymbol {N}}&={\begin{bmatrix}{\boldsymbol {A}}_{1}&{\boldsymbol {A}}_{2}&{\boldsymbol {A}}_{5}\end{bmatrix}}.\end{aligned}}}" loading="lazy"></span></dd></dl>

<p>Correspondingly,

</p>

<mtr>

<mtd>

</mrow>

</mtd>

<mtd>

<msup>

<mrow>

<mtr>

<mtd>

</mtd>

<mtd>

</mtd>

<mtd>

</mtd>

<mtd>

</mtd>

<mtd>

</mtd>

</mtr>

</mtable>

</mrow>

</mrow>

</msup>

</mtd>

</mtr>

<mtr>

<mtd>

</mrow>

</mtd>

<mtd>

<msup>

<mrow>

<mtr>

<mtd>

</mtd>

<mtd>

</mrow>

</mtd>

</mtr>

</mtable>

</mrow>

</mrow>

</msup>

</mtd>

</mtr>

<mtr>

<mtd>

<msub>

</mrow>

</msub>

</mrow>

</mtd>

<mtd>

<msup>

<mrow>

<mtr>

<mtd>

</mrow>

</mtd>

<mtd>

</mrow>

</mtd>

<mtd>

</mrow>

</mtd>

</mtr>

</mtable>

</mrow>

</mrow>

</msup>

</mtd>

</mtr>

</mtable>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle {\begin{aligned}{\boldsymbol {x}}&={\begin{bmatrix}0&0&5&5&0\end{bmatrix}}^{\mathrm {T} },\\{\boldsymbol {\lambda }}&={\begin{bmatrix}0&-4/3\end{bmatrix}}^{\mathrm {T} },\\{\boldsymbol {s_{N}}}&={\begin{bmatrix}2/3&11/3&4/3\end{bmatrix}}^{\mathrm {T} }.\end{aligned}}}</annotation>

</semantics>

</math></span><img src="./a44aa8526a43227f93b6c00cd69a0dae23506cfd.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -4.671ex; width:27.385ex; height:10.509ex;" alt="{\displaystyle {\begin{aligned}{\boldsymbol {x}}&={\begin{bmatrix}0&0&5&5&0\end{bmatrix}}^{\mathrm {T} },\\{\boldsymbol {\lambda }}&={\begin{bmatrix}0&-4/3\end{bmatrix}}^{\mathrm {T} },\\{\boldsymbol {s_{N}}}&={\begin{bmatrix}2/3&11/3&4/3\end{bmatrix}}^{\mathrm {T} }.\end{aligned}}}" loading="lazy"></span></dd></dl>

<p>A positive <span class="texhtml"><i><b>s<sub>N</sub></b></i></span> indicates that <span class="texhtml"><i><b>x</b></i></span> is now optimal.

</p>

<div class="mw-heading mw-heading2"><h2 id="Practical_issues">Practical issues</h2></div>

<div class="mw-heading mw-heading3"><h3 id="Degeneracy">Degeneracy</h3></div>

<div role="note" class="hatnote navigation-not-searchable">See also: <a href="Simplex_method" class="mw-redirect" title="Simplex method">Simplex method § Degeneracy: stalling and cycling</a></div>

<p>Because the revised simplex method is mathematically equivalent to the simplex method, it also suffers from degeneracy, where a pivot operation does not result in a decrease in <span class="texhtml"><i><b>c</b></i><sup>T</sup><i><b>x</b></i></span>, and a chain of pivot operations causes the basis to cycle. A perturbation or lexicographic strategy can be used to prevent cycling and guarantee termination.<sup id="cite_ref-FOOTNOTENocedalWright2006381§13.5_7-0" class="reference"><a href="#cite_note-FOOTNOTENocedalWright2006381§13.5-7"><span class="cite-bracket">[</span>6<span class="cite-bracket">]</span></a></sup>

</p>

<div class="mw-heading mw-heading3"><h3 id="Basis_representation">Basis representation</h3></div>

<p>Two types of <a href="System_of_linear_equations" title="System of linear equations">linear systems</a> involving <span class="texhtml"><i><b>B</b></i></span> are present in the revised simplex method:

</p>

<mtr>

<mtd>

</mrow>

</mtd>

<mtd>

</mrow>

</mtd>

</mtr>

<mtr>

<mtd>

<msup>

</mrow>

</mrow>

</msup>

</mrow>

</mtd>

<mtd>

</mrow>

</mtd>

</mtr>

</mtable>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle {\begin{aligned}{\boldsymbol {Bz}}&={\boldsymbol {y}},\\{\boldsymbol {B}}^{\mathrm {T} }{\boldsymbol {z}}&={\boldsymbol {y}}.\end{aligned}}}</annotation>

</semantics>

</math></span><img src="./0d6dbeac8e7e0dc1933dee171efe3bfb2adc3213.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -2.206ex; margin-bottom: -0.299ex; width:10.59ex; height:6.176ex;" alt="{\displaystyle {\begin{aligned}{\boldsymbol {Bz}}&={\boldsymbol {y}},\\{\boldsymbol {B}}^{\mathrm {T} }{\boldsymbol {z}}&={\boldsymbol {y}}.\end{aligned}}}" loading="lazy"></span></dd></dl>

<p>Instead of refactorizing <span class="texhtml"><i><b>B</b></i></span>, usually an <a href="LU_factorization" class="mw-redirect" title="LU factorization">LU factorization</a> is directly updated after each pivot operation, for which purpose there exist several strategies such as the Forrest−Tomlin and Bartels−Golub methods. However, the amount of data representing the updates as well as numerical errors builds up over time and makes periodic refactorization necessary.<sup id="cite_ref-FOOTNOTEMorgan1997§2_1-1" class="reference"><a href="#cite_note-FOOTNOTEMorgan1997§2-1"><span class="cite-bracket">[</span>1<span class="cite-bracket">]</span></a></sup><sup id="cite_ref-FOOTNOTENocedalWright2006372§13.4_8-0" class="reference"><a href="#cite_note-FOOTNOTENocedalWright2006372§13.4-8"><span class="cite-bracket">[</span>7<span class="cite-bracket">]</span></a></sup>

</p>

<div class="mw-heading mw-heading2"><h2 id="Notes_and_references">Notes and references</h2></div>

<div class="mw-heading mw-heading3"><h3 id="Notes">Notes</h3></div>

/* start https://en.wikipedia.org/ */

.mw-parser-output .reflist{margin-bottom:0.5em;list-style-type:decimal}@media screen{.mw-parser-output .reflist{font-size:90%}}.mw-parser-output .reflist .references{font-size:100%;margin-bottom:0;list-style-type:inherit}.mw-parser-output .reflist-columns-2{column-width:30em}.mw-parser-output .reflist-columns-3{column-width:25em}.mw-parser-output .reflist-columns{margin-top:0.3em}.mw-parser-output .reflist-columns ol{margin-top:0}.mw-parser-output .reflist-columns li{page-break-inside:avoid;break-inside:avoid-column}.mw-parser-output .reflist-upper-alpha{list-style-type:upper-alpha}.mw-parser-output .reflist-upper-roman{list-style-type:upper-roman}.mw-parser-output .reflist-lower-alpha{list-style-type:lower-alpha}.mw-parser-output .reflist-lower-greek{list-style-type:lower-greek}.mw-parser-output .reflist-lower-roman{list-style-type:lower-roman}

/* end https://en.wikipedia.org/ */

</style><div class="reflist reflist-lower-alpha">

<li id="cite_note-4"><span class="mw-cite-backlink"><b><a href="#cite_ref-4">^</a></b></span> <span class="reference-text">The same theorem also states that the feasible polytope has at least one vertex and that there is at least one vertex which is optimal.<sup id="cite_ref-FOOTNOTENocedalWright2006363Theorem&nbsp;13.2_3-0" class="reference"><a href="#cite_note-FOOTNOTENocedalWright2006363Theorem&nbsp;13.2-3"><span class="cite-bracket">[</span>3<span class="cite-bracket">]</span></a></sup></span>

</li>

</ol></div></div>

<div class="mw-heading mw-heading3"><h3 id="References">References</h3></div>

<li id="cite_note-FOOTNOTEMorgan1997§2-1"><span class="mw-cite-backlink">^ <a href="#cite_ref-FOOTNOTEMorgan1997§2_1-0"><sup><i><b>a</b></i></sup></a> <a href="#cite_ref-FOOTNOTEMorgan1997§2_1-1"><sup><i><b>b</b></i></sup></a></span> <span class="reference-text"><a href="#CITEREFMorgan1997">Morgan 1997</a>, §2.</span>

</li>

<li id="cite_note-FOOTNOTENocedalWright2006358Eq.&nbsp;13.4-2"><span class="mw-cite-backlink"><b><a href="#cite_ref-FOOTNOTENocedalWright2006358Eq.&nbsp;13.4_2-0">^</a></b></span> <span class="reference-text"><a href="#CITEREFNocedalWright2006">Nocedal & Wright 2006</a>, p. 358, Eq. 13.4.</span>

</li>

<li id="cite_note-FOOTNOTENocedalWright2006363Theorem&nbsp;13.2-3"><span class="mw-cite-backlink"><b><a href="#cite_ref-FOOTNOTENocedalWright2006363Theorem&nbsp;13.2_3-0">^</a></b></span> <span class="reference-text"><a href="#CITEREFNocedalWright2006">Nocedal & Wright 2006</a>, p. 363, Theorem 13.2.</span>

</li>

<li id="cite_note-FOOTNOTENocedalWright2006370Theorem&nbsp;13.4-5"><span class="mw-cite-backlink"><b><a href="#cite_ref-FOOTNOTENocedalWright2006370Theorem&nbsp;13.4_5-0">^</a></b></span> <span class="reference-text"><a href="#CITEREFNocedalWright2006">Nocedal & Wright 2006</a>, p. 370, Theorem 13.4.</span>

</li>

<li id="cite_note-FOOTNOTENocedalWright2006369Eq.&nbsp;13.24-6"><span class="mw-cite-backlink"><b><a href="#cite_ref-FOOTNOTENocedalWright2006369Eq.&nbsp;13.24_6-0">^</a></b></span> <span class="reference-text"><a href="#CITEREFNocedalWright2006">Nocedal & Wright 2006</a>, p. 369, Eq. 13.24.</span>

</li>

<li id="cite_note-FOOTNOTENocedalWright2006381§13.5-7"><span class="mw-cite-backlink"><b><a href="#cite_ref-FOOTNOTENocedalWright2006381§13.5_7-0">^</a></b></span> <span class="reference-text"><a href="#CITEREFNocedalWright2006">Nocedal & Wright 2006</a>, p. 381, §13.5.</span>

</li>

<li id="cite_note-FOOTNOTENocedalWright2006372§13.4-8"><span class="mw-cite-backlink"><b><a href="#cite_ref-FOOTNOTENocedalWright2006372§13.4_8-0">^</a></b></span> <span class="reference-text"><a href="#CITEREFNocedalWright2006">Nocedal & Wright 2006</a>, p. 372, §13.4.</span>

</li>

</ol></div>

<div class="mw-heading mw-heading3"><h3 id="Bibliography">Bibliography</h3></div>

/* start https://en.wikipedia.org/ */

.mw-parser-output .refbegin{margin-bottom:0.5em}.mw-parser-output .refbegin-hanging-indents>ul{margin-left:0}.mw-parser-output .refbegin-hanging-indents>ul>li{margin-left:0;padding-left:3.2em;text-indent:-3.2em}.mw-parser-output .refbegin-hanging-indents ul,.mw-parser-output .refbegin-hanging-indents ul li{list-style:none}@media(max-width:720px){.mw-parser-output .refbegin-hanging-indents>ul>li{padding-left:1.6em;text-indent:-1.6em}}.mw-parser-output .refbegin-columns{margin-top:0.3em}.mw-parser-output .refbegin-columns ul{margin-top:0}.mw-parser-output .refbegin-columns li{page-break-inside:avoid;break-inside:avoid-column}@media screen{.mw-parser-output .refbegin{font-size:90%}}

/* end https://en.wikipedia.org/ */

</style><div class="refbegin" style="">

/* start https://en.wikipedia.org/ */

.mw-parser-output cite.citation{font-style:inherit;word-wrap:break-word}.mw-parser-output .citation q{quotes:"\"""\"""'""'"}.mw-parser-output .citation:target{background-color:rgba(0,127,255,0.133)}.mw-parser-output .id-lock-free.id-lock-free a{background:url("./mw/Lock-green.svg")right 0.1em center/9px no-repeat}.mw-parser-output .id-lock-limited.id-lock-limited a,.mw-parser-output .id-lock-registration.id-lock-registration a{background:url("./mw/Lock-gray-alt-2.svg")right 0.1em center/9px no-repeat}.mw-parser-output .id-lock-subscription.id-lock-subscription a{background:url("./mw/Lock-red-alt-2.svg")right 0.1em center/9px no-repeat}.mw-parser-output .cs1-ws-icon a{background:url("./mw/Wikisource-logo.svg")right 0.1em center/12px no-repeat}body:not(.skin-timeless):not(.skin-minerva) .mw-parser-output .id-lock-free a,body:not(.skin-timeless):not(.skin-minerva) .mw-parser-output .id-lock-limited a,body:not(.skin-timeless):not(.skin-minerva) .mw-parser-output .id-lock-registration a,body:not(.skin-timeless):not(.skin-minerva) .mw-parser-output .id-lock-subscription a,body:not(.skin-timeless):not(.skin-minerva) .mw-parser-output .cs1-ws-icon a{background-size:contain;padding:0 1em 0 0}.mw-parser-output .cs1-code{color:inherit;background:inherit;border:none;padding:inherit}.mw-parser-output .cs1-hidden-error{display:none;color:var(--color-error,#d33)}.mw-parser-output .cs1-visible-error{color:var(--color-error,#d33)}.mw-parser-output .cs1-maint{display:none;color:#085;margin-left:0.3em}.mw-parser-output .cs1-kern-left{padding-left:0.2em}.mw-parser-output .cs1-kern-right{padding-right:0.2em}.mw-parser-output .citation .mw-selflink{font-weight:inherit}@media screen{.mw-parser-output .cs1-format{font-size:95%}html.skin-theme-clientpref-night .mw-parser-output .cs1-maint{color:#18911f}}@media screen and (prefers-color-scheme:dark){html.skin-theme-clientpref-os .mw-parser-output .cs1-maint{color:#18911f}}

/* end https://en.wikipedia.org/ */

</style><cite id="CITEREFMorgan1997" class="citation thesis cs1">Morgan, S. S. (1997). <a rel="nofollow" class="external text" href="https://web.archive.org/web/20110807134509/http://www.cise.ufl.edu/research/sparse/Morgan/index.htm"><i>A Comparison of Simplex Method Algorithms</i></a> (MSc thesis). <a href="University_of_Florida" title="University of Florida">University of Florida</a>. Archived from <a rel="nofollow" class="external text" href="http://www.cise.ufl.edu/research/sparse/Morgan/index.htm">the original</a> on 7 August 2011.</cite></li>

<li><cite id="CITEREFNocedalWright2006" class="citation book cs1">Nocedal, J.; Wright, S. J. (2006). Mikosch, T. V.; Resnick, S. I.; Robinson, S. M. (eds.). <a rel="nofollow" class="external text" href="https://www.springer.com/mathematics/book/978-0-387-30303-1"><i>Numerical Optimization</i></a>. Springer Series in Operations Research and Financial Engineering (2nd ed.). New York, NY, USA: <a href="Springer_Science%2BBusiness_Media" title="Springer Science+Business Media">Springer</a>. <a href="ISBN_(identifier)" class="mw-redirect" title="ISBN (identifier)">ISBN</a> <bdi>978-0-387-30303-1</bdi>.</cite></li></ul>

</div>

/* start https://en.wikipedia.org/ */

.mw-parser-output .hlist dl,.mw-parser-output .hlist ol,.mw-parser-output .hlist ul{margin:0;padding:0}.mw-parser-output .hlist dd,.mw-parser-output .hlist dt,.mw-parser-output .hlist li{margin:0;display:inline}.mw-parser-output .hlist.inline,.mw-parser-output .hlist.inline dl,.mw-parser-output .hlist.inline ol,.mw-parser-output .hlist.inline ul,.mw-parser-output .hlist dl dl,.mw-parser-output .hlist dl ol,.mw-parser-output .hlist dl ul,.mw-parser-output .hlist ol dl,.mw-parser-output .hlist ol ol,.mw-parser-output .hlist ol ul,.mw-parser-output .hlist ul dl,.mw-parser-output .hlist ul ol,.mw-parser-output .hlist ul ul{display:inline}.mw-parser-output .hlist .mw-empty-li{display:none}.mw-parser-output .hlist dt::after{content:": "}.mw-parser-output .hlist dd::after,.mw-parser-output .hlist li::after{content:" · ";font-weight:bold}.mw-parser-output .hlist dd:last-child::after,.mw-parser-output .hlist dt:last-child::after,.mw-parser-output .hlist li:last-child::after{content:none}.mw-parser-output .hlist dd dd:first-child::before,.mw-parser-output .hlist dd dt:first-child::before,.mw-parser-output .hlist dd li:first-child::before,.mw-parser-output .hlist dt dd:first-child::before,.mw-parser-output .hlist dt dt:first-child::before,.mw-parser-output .hlist dt li:first-child::before,.mw-parser-output .hlist li dd:first-child::before,.mw-parser-output .hlist li dt:first-child::before,.mw-parser-output .hlist li li:first-child::before{content:" (";font-weight:normal}.mw-parser-output .hlist dd dd:last-child::after,.mw-parser-output .hlist dd dt:last-child::after,.mw-parser-output .hlist dd li:last-child::after,.mw-parser-output .hlist dt dd:last-child::after,.mw-parser-output .hlist dt dt:last-child::after,.mw-parser-output .hlist dt li:last-child::after,.mw-parser-output .hlist li dd:last-child::after,.mw-parser-output .hlist li dt:last-child::after,.mw-parser-output .hlist li li:last-child::after{content:")";font-weight:normal}.mw-parser-output .hlist ol{counter-reset:listitem}.mw-parser-output .hlist ol>li{counter-increment:listitem}.mw-parser-output .hlist ol>li::before{content:" "counter(listitem)"\a0 "}.mw-parser-output .hlist dd ol>li:first-child::before,.mw-parser-output .hlist dt ol>li:first-child::before,.mw-parser-output .hlist li ol>li:first-child::before{content:" ("counter(listitem)"\a0 "}

/* end https://en.wikipedia.org/ */

</style><style data-mw-deduplicate="TemplateStyles:r1236075235">

/* start https://en.wikipedia.org/ */

.mw-parser-output .navbox{box-sizing:border-box;border:1px solid #a2a9b1;width:100%;clear:both;font-size:88%;text-align:center;padding:1px;margin:1em auto 0}.mw-parser-output .navbox .navbox{margin-top:0}.mw-parser-output .navbox+.navbox,.mw-parser-output .navbox+.navbox-styles+.navbox{margin-top:-1px}.mw-parser-output .navbox-inner,.mw-parser-output .navbox-subgroup{width:100%}.mw-parser-output .navbox-group,.mw-parser-output .navbox-title,.mw-parser-output .navbox-abovebelow{padding:0.25em 1em;line-height:1.5em;text-align:center}.mw-parser-output .navbox-group{white-space:nowrap;text-align:right}.mw-parser-output .navbox,.mw-parser-output .navbox-subgroup{background-color:#fdfdfd}.mw-parser-output .navbox-list{line-height:1.5em;border-color:#fdfdfd}.mw-parser-output .navbox-list-with-group{text-align:left;border-left-width:2px;border-left-style:solid}.mw-parser-output tr+tr>.navbox-abovebelow,.mw-parser-output tr+tr>.navbox-group,.mw-parser-output tr+tr>.navbox-image,.mw-parser-output tr+tr>.navbox-list{border-top:2px solid #fdfdfd}.mw-parser-output .navbox-title{background-color:#ccf}.mw-parser-output .navbox-abovebelow,.mw-parser-output .navbox-group,.mw-parser-output .navbox-subgroup .navbox-title{background-color:#ddf}.mw-parser-output .navbox-subgroup .navbox-group,.mw-parser-output .navbox-subgroup .navbox-abovebelow{background-color:#e6e6ff}.mw-parser-output .navbox-even{background-color:#f7f7f7}.mw-parser-output .navbox-odd{background-color:transparent}.mw-parser-output .navbox .hlist td dl,.mw-parser-output .navbox .hlist td ol,.mw-parser-output .navbox .hlist td ul,.mw-parser-output .navbox td.hlist dl,.mw-parser-output .navbox td.hlist ol,.mw-parser-output .navbox td.hlist ul{padding:0.125em 0}.mw-parser-output .navbox .navbar{display:block;font-size:100%}.mw-parser-output .navbox-title .navbar{float:left;text-align:left;margin-right:0.5em}body.skin--responsive .mw-parser-output .navbox-image img{max-width:none!important}@media print{body.ns-0 .mw-parser-output .navbox{display:none!important}}

/* end https://en.wikipedia.org/ */

</style></div><div role="navigation" class="navbox" aria-labelledby="Optimization:_Algorithms,_methods,_and_heuristics381" style="padding:3px"><table class="nowraplinks hlist mw-collapsible uncollapsed navbox-inner" style="border-spacing:0;background:transparent;color:inherit"><tbody><tr><th scope="col" class="navbox-title" colspan="3"><style data-mw-deduplicate="TemplateStyles:r1239400231">

/* start https://en.wikipedia.org/ */

.mw-parser-output .navbar{display:inline;font-size:88%;font-weight:normal}.mw-parser-output .navbar-collapse{float:left;text-align:left}.mw-parser-output .navbar-boxtext{word-spacing:0}.mw-parser-output .navbar ul{display:inline-block;white-space:nowrap;line-height:inherit}.mw-parser-output .navbar-brackets::before{margin-right:-0.125em;content:"[ "}.mw-parser-output .navbar-brackets::after{margin-left:-0.125em;content:" ]"}.mw-parser-output .navbar li{word-spacing:-0.125em}.mw-parser-output .navbar a>span,.mw-parser-output .navbar a>abbr{text-decoration:inherit}.mw-parser-output .navbar-mini abbr{font-variant:small-caps;border-bottom:none;text-decoration:none;cursor:inherit}.mw-parser-output .navbar-ct-full{font-size:114%;margin:0 7em}.mw-parser-output .navbar-ct-mini{font-size:114%;margin:0 4em}html.skin-theme-clientpref-night .mw-parser-output .navbar li a abbr{color:var(--color-base)!important}@media(prefers-color-scheme:dark){html.skin-theme-clientpref-os .mw-parser-output .navbar li a abbr{color:var(--color-base)!important}}@media print{.mw-parser-output .navbar{display:none!important}}

/* end https://en.wikipedia.org/ */

</style><div id="Optimization:_Algorithms,_methods,_and_heuristics381" style="font-size:114%;margin:0 4em"><a href="Mathematical_optimization" title="Mathematical optimization">Optimization</a>: <a href="Optimization_algorithm" class="mw-redirect" title="Optimization algorithm">Algorithms</a>, <a href="Iterative_method" title="Iterative method">methods</a>, and <a href="Heuristic_algorithm" class="mw-redirect" title="Heuristic algorithm">heuristics</a></div></th></tr><tr><td colspan="2" class="navbox-list navbox-odd" style="width:100%;padding:0"><div style="padding:0 0.25em"></div><table class="nowraplinks mw-collapsible mw-collapsed navbox-subgroup" style="border-spacing:0"><tbody><tr><th scope="col" class="navbox-title" colspan="2"><div id="Unconstrained_nonlinear381" style="font-size:114%;margin:0 4em"><a href="Nonlinear_programming" title="Nonlinear programming">Unconstrained nonlinear</a></div></th></tr><tr><td colspan="2" class="navbox-list navbox-odd" style="width:100%;padding:0"><div style="padding:0 0.25em"></div><table class="nowraplinks navbox-subgroup" style="border-spacing:0"><tbody><tr><th scope="row" class="navbox-group" style="width:1%"><a href="Function_(mathematics)" title="Function (mathematics)">Functions</a></th><td class="navbox-list-with-group navbox-list navbox-odd" style="width:100%;padding:0"><div style="padding:0 0.25em">

<ul><li><a href="Golden-section_search" title="Golden-section search">Golden-section search</a></li>

<li><a href="Powell's_method" title="Powell's method">Powell's method</a></li>

<li><a href="Line_search" title="Line search">Line search</a></li>

<li><a href="Nelder%E2%80%93Mead_method" title="Nelder–Mead method">Nelder–Mead method</a></li>

<li><a href="Successive_parabolic_interpolation" title="Successive parabolic interpolation">Successive parabolic interpolation</a></li></ul>

</div></td></tr><tr><th scope="row" class="navbox-group" style="width:1%"><a href="Gradient" title="Gradient">Gradients</a></th><td class="navbox-list-with-group navbox-list navbox-odd" style="width:100%;padding:0"><div style="padding:0 0.25em"></div><table class="nowraplinks navbox-subgroup" style="border-spacing:0"><tbody><tr><th scope="row" class="navbox-group" style="width:1%"><a href="Local_convergence" title="Local convergence">Convergence</a></th><td class="navbox-list-with-group navbox-list navbox-even" style="width:100%;padding:0"><div style="padding:0 0.25em">

<ul><li><a href="Trust_region" title="Trust region">Trust region</a></li>

<li><a href="Wolfe_conditions" title="Wolfe conditions">Wolfe conditions</a></li></ul>

</div></td></tr><tr><th scope="row" class="navbox-group" style="width:1%"><a href="Quasi-Newton_method" title="Quasi-Newton method">Quasi–Newton</a></th><td class="navbox-list-with-group navbox-list navbox-odd" style="width:100%;padding:0"><div style="padding:0 0.25em">

<ul><li><a href="Berndt%E2%80%93Hall%E2%80%93Hall%E2%80%93Hausman_algorithm" title="Berndt–Hall–Hall–Hausman algorithm">Berndt–Hall–Hall–Hausman</a></li>

<li><a href="Broyden%E2%80%93Fletcher%E2%80%93Goldfarb%E2%80%93Shanno_algorithm" title="Broyden–Fletcher–Goldfarb–Shanno algorithm">Broyden–Fletcher–Goldfarb–Shanno</a> and <a href="Limited-memory_BFGS" title="Limited-memory BFGS">L-BFGS</a></li>

<li><a href="Davidon%E2%80%93Fletcher%E2%80%93Powell_formula" title="Davidon–Fletcher–Powell formula">Davidon–Fletcher–Powell</a></li>

<li><a href="Symmetric_rank-one" title="Symmetric rank-one">Symmetric rank-one (SR1)</a></li></ul>

</div></td></tr><tr><th scope="row" class="navbox-group" style="width:1%"><a href="Iterative_method" title="Iterative method">Other methods</a></th><td class="navbox-list-with-group navbox-list navbox-even" style="width:100%;padding:0"><div style="padding:0 0.25em">

<ul><li><a href="Nonlinear_conjugate_gradient_method" title="Nonlinear conjugate gradient method">Conjugate gradient</a></li>

<li><a href="Gauss%E2%80%93Newton_algorithm" title="Gauss–Newton algorithm">Gauss–Newton</a></li>

<li><a href="Gradient_descent" title="Gradient descent">Gradient</a></li>

<li><a href="Mirror_descent" title="Mirror descent">Mirror</a></li>

<li><a href="Levenberg%E2%80%93Marquardt_algorithm" title="Levenberg–Marquardt algorithm">Levenberg–Marquardt</a></li>

<li><a href="Powell's_dog_leg_method" title="Powell's dog leg method">Powell's dog leg method</a></li>

<li><a href="Truncated_Newton_method" title="Truncated Newton method">Truncated Newton</a></li></ul>

</div></td></tr></tbody></table><div></div></td></tr><tr><th scope="row" class="navbox-group" style="width:1%"><a href="Hessian_matrix" title="Hessian matrix">Hessians</a></th><td class="navbox-list-with-group navbox-list navbox-odd" style="width:100%;padding:0"><div style="padding:0 0.25em">

<ul><li><a href="Newton's_method_in_optimization" title="Newton's method in optimization">Newton's method</a></li></ul>

</div></td></tr></tbody></table><div></div></td></tr></tbody></table><div></div></td><td class="noviewer navbox-image" rowspan="5" style="width:1px;padding:0 0 0 2px"><div></div></td></tr><tr><td colspan="2" class="navbox-list navbox-odd" style="width:100%;padding:0"><div style="padding:0 0.25em"></div><table class="nowraplinks mw-collapsible mw-collapsed navbox-subgroup" style="border-spacing:0"><tbody><tr><th scope="col" class="navbox-title" colspan="2"><div id="Constrained_nonlinear381" style="font-size:114%;margin:0 4em"><a href="Nonlinear_programming" title="Nonlinear programming">Constrained nonlinear</a></div></th></tr><tr><td colspan="2" class="navbox-list navbox-odd" style="width:100%;padding:0"><div style="padding:0 0.25em"></div><table class="nowraplinks navbox-subgroup" style="border-spacing:0"><tbody><tr><th scope="row" class="navbox-group" style="width:1%">General</th><td class="navbox-list-with-group navbox-list navbox-odd" style="width:100%;padding:0"><div style="padding:0 0.25em">

<ul><li><a href="Barrier_function" title="Barrier function">Barrier methods</a></li>

<li><a href="Penalty_method" title="Penalty method">Penalty methods</a></li></ul>

</div></td></tr><tr><th scope="row" class="navbox-group" style="width:1%">Differentiable</th><td class="navbox-list-with-group navbox-list navbox-even" style="width:100%;padding:0"><div style="padding:0 0.25em">

<ul><li><a href="Augmented_Lagrangian_method" title="Augmented Lagrangian method">Augmented Lagrangian methods</a></li>

<li><a href="Sequential_quadratic_programming" title="Sequential quadratic programming">Sequential quadratic programming</a></li>

<li><a href="Successive_linear_programming" title="Successive linear programming">Successive linear programming</a></li></ul>

</div></td></tr></tbody></table><div></div></td></tr></tbody></table><div></div></td></tr><tr><td colspan="2" class="navbox-list navbox-odd" style="width:100%;padding:0"><div style="padding:0 0.25em"></div><table class="nowraplinks mw-collapsible uncollapsed navbox-subgroup" style="border-spacing:0"><tbody><tr><th scope="col" class="navbox-title" colspan="2"><div id="Convex_optimization381" style="font-size:114%;margin:0 4em"><a href="Convex_optimization" title="Convex optimization">Convex optimization</a></div></th></tr><tr><td colspan="2" class="navbox-list navbox-odd" style="width:100%;padding:0"><div style="padding:0 0.25em"></div><table class="nowraplinks navbox-subgroup" style="border-spacing:0"><tbody><tr><th scope="row" class="navbox-group" style="width:1%"><a href="Convex_minimization" class="mw-redirect" title="Convex minimization">Convex<br> minimization</a></th><td class="navbox-list-with-group navbox-list navbox-odd" style="width:100%;padding:0"><div style="padding:0 0.25em">

<ul><li><a href="Cutting-plane_method" title="Cutting-plane method">Cutting-plane method</a></li>

<li><a href="Frank%E2%80%93Wolfe_algorithm" title="Frank–Wolfe algorithm">Reduced gradient (Frank–Wolfe)</a></li>

<li><a href="Subgradient_method" title="Subgradient method">Subgradient method</a></li></ul>

</div></td></tr><tr><th scope="row" class="navbox-group" style="width:1%"><a href="Linear_programming" title="Linear programming">Linear</a> and<br><a href="Quadratic_programming" title="Quadratic programming">quadratic</a></th><td class="navbox-list-with-group navbox-list navbox-odd" style="width:100%;padding:0"><div style="padding:0 0.25em"></div><table class="nowraplinks navbox-subgroup" style="border-spacing:0"><tbody><tr><th scope="row" class="navbox-group" style="width:1%"><a href="Linear_programming#Interior_point" title="Linear programming">Interior point</a></th><td class="navbox-list-with-group navbox-list navbox-even" style="width:100%;padding:0"><div style="padding:0 0.25em">

<ul><li><a href="Affine_scaling" title="Affine scaling">Affine scaling</a></li>

<li><a href="Ellipsoid_method" title="Ellipsoid method">Ellipsoid algorithm of Khachiyan</a></li>

<li><a href="Karmarkar's_algorithm" title="Karmarkar's algorithm">Projective algorithm of Karmarkar</a></li></ul>

</div></td></tr><tr><th scope="row" class="navbox-group" style="width:1%"><a href="Matroid" title="Matroid">Basis-</a><a href="Exchange_algorithm" class="mw-redirect" title="Exchange algorithm">exchange</a></th><td class="navbox-list-with-group navbox-list navbox-odd" style="width:100%;padding:0"><div style="padding:0 0.25em">

<ul><li><a href="Simplex_algorithm" title="Simplex algorithm">Simplex algorithm of Dantzig</a></li>

<li><a href="Criss-cross_algorithm" title="Criss-cross algorithm">Criss-cross algorithm</a></li>

<li><a href="Lemke's_algorithm" title="Lemke's algorithm">Principal pivoting algorithm of Lemke</a></li>

<li><a href="Active-set_method" title="Active-set method">Active-set method</a></li></ul>

</div></td></tr></tbody></table><div></div></td></tr></tbody></table><div></div></td></tr></tbody></table><div></div></td></tr><tr><td colspan="2" class="navbox-list navbox-odd" style="width:100%;padding:0"><div style="padding:0 0.25em"></div><table class="nowraplinks mw-collapsible mw-collapsed navbox-subgroup" style="border-spacing:0"><tbody><tr><th scope="col" class="navbox-title" colspan="2"><div id="Combinatorial381" style="font-size:114%;margin:0 4em"><a href="Combinatorial_optimization" title="Combinatorial optimization">Combinatorial</a></div></th></tr><tr><td colspan="2" class="navbox-list navbox-odd" style="width:100%;padding:0"><div style="padding:0 0.25em"></div><table class="nowraplinks navbox-subgroup" style="border-spacing:0"><tbody><tr><th scope="row" class="navbox-group" style="width:1%">Paradigms</th><td class="navbox-list-with-group navbox-list navbox-odd" style="width:100%;padding:0"><div style="padding:0 0.25em">

<ul><li><a href="Approximation_algorithm" title="Approximation algorithm">Approximation algorithm</a></li>

<li><a href="Dynamic_programming" title="Dynamic programming">Dynamic programming</a></li>

<li><a href="Greedy_algorithm" title="Greedy algorithm">Greedy algorithm</a></li>

<li><a href="Integer_programming" title="Integer programming">Integer programming</a>

<ul><li><a href="Branch_and_bound" title="Branch and bound">Branch and bound</a>/<a href="Branch_and_cut" title="Branch and cut">cut</a></li></ul></li></ul>

</div></td></tr><tr><th scope="row" class="navbox-group" style="width:1%"><a href="Graph_algorithm" class="mw-redirect" title="Graph algorithm">Graph<br> algorithms</a></th><td class="navbox-list-with-group navbox-list navbox-odd" style="width:100%;padding:0"><div style="padding:0 0.25em"></div><table class="nowraplinks navbox-subgroup" style="border-spacing:0"><tbody><tr><th id="Minimum_spanning_tree52" scope="row" class="navbox-group" style="width:1%"><a href="Minimum_spanning_tree" title="Minimum spanning tree">Minimum<br> spanning tree</a></th><td class="navbox-list-with-group navbox-list navbox-even" style="width:100%;padding:0"><div style="padding:0 0.25em">

<ul><li><a href="Bor%C5%AFvka's_algorithm" title="Borůvka's algorithm">Borůvka</a></li>

<li><a href="Kruskal's_algorithm" title="Kruskal's algorithm">Kruskal</a></li></ul>

</div></td></tr></tbody></table><div>

</div><table class="nowraplinks navbox-subgroup" style="border-spacing:0"><tbody><tr><th id="Shortest_path39" scope="row" class="navbox-group" style="width:1%"><a href="Shortest_path_problem" title="Shortest path problem">Shortest path</a></th><td class="navbox-list-with-group navbox-list navbox-odd" style="width:100%;padding:0"><div style="padding:0 0.25em">

<ul><li><a href="Bellman%E2%80%93Ford_algorithm" title="Bellman–Ford algorithm">Bellman–Ford</a>

<li><a href="Dijkstra's_algorithm" title="Dijkstra's algorithm">Dijkstra</a></li>

<li><a href="Floyd%E2%80%93Warshall_algorithm" title="Floyd–Warshall algorithm">Floyd–Warshall</a></li></ul>

</div></td></tr></tbody></table><div></div></td></tr><tr><th scope="row" class="navbox-group" style="width:1%"><a href="Flow_network" title="Flow network">Network flows</a></th><td class="navbox-list-with-group navbox-list navbox-even" style="width:100%;padding:0"><div style="padding:0 0.25em">

<ul><li><a href="Dinic's_algorithm" title="Dinic's algorithm">Dinic</a></li>

<li><a href="Edmonds%E2%80%93Karp_algorithm" title="Edmonds–Karp algorithm">Edmonds–Karp</a></li>

<li><a href="Ford%E2%80%93Fulkerson_algorithm" title="Ford–Fulkerson algorithm">Ford–Fulkerson</a></li>

<li><a href="Push%E2%80%93relabel_maximum_flow_algorithm" title="Push–relabel maximum flow algorithm">Push–relabel maximum flow</a></li></ul>

</div></td></tr></tbody></table><div></div></td></tr></tbody></table><div></div></td></tr><tr><td colspan="2" class="navbox-list navbox-odd" style="width:100%;padding:0"><div style="padding:0 0.25em"></div><table class="nowraplinks mw-collapsible mw-collapsed navbox-subgroup" style="border-spacing:0"><tbody><tr><th scope="col" class="navbox-title" colspan="2"><div id="Metaheuristics381" style="font-size:114%;margin:0 4em"><a href="Metaheuristic" title="Metaheuristic">Metaheuristics</a></div></th></tr><tr><td colspan="2" class="navbox-list navbox-odd" style="width:100%;padding:0"><div style="padding:0 0.25em">

<ul><li><a href="Evolutionary_algorithm" title="Evolutionary algorithm">Evolutionary algorithm</a></li>

<li><a href="Hill_climbing" title="Hill climbing">Hill climbing</a></li>

<li><a href="Local_search_(optimization)" title="Local search (optimization)">Local search</a></li>

<li><a href="Parallel_metaheuristic" title="Parallel metaheuristic">Parallel metaheuristics</a></li>

<li><a href="Simulated_annealing" title="Simulated annealing">Simulated annealing</a></li>

<li><a href="Spiral_optimization_algorithm" title="Spiral optimization algorithm">Spiral optimization algorithm</a></li>

<li><a href="Tabu_search" title="Tabu search">Tabu search</a></li></ul>

</div></td></tr></tbody></table><div></div></td></tr><tr><td class="navbox-abovebelow" colspan="3"><div>

<ul><li><a href="Comparison_of_optimization_software" title="Comparison of optimization software">Software</a></li></ul>

</div></td></tr></tbody></table></div>

<div class="navbox-styles"></div><div role="navigation" class="navbox" aria-labelledby="Complementarity_problems_and_algorithms137" style="padding:3px"><table class="nowraplinks mw-collapsible autocollapse navbox-inner" style="border-spacing:0;background:transparent;color:inherit"><tbody><tr><th scope="col" class="navbox-title" colspan="2"><div id="Complementarity_problems_and_algorithms137" style="font-size:114%;margin:0 4em"><a href="Optimization_(mathematics)" class="mw-redirect" title="Optimization (mathematics)"> Complementarity problems and algorithms</a></div></th></tr><tr><th scope="row" class="navbox-group" style="width:1%">Complementarity Problems</th><td class="navbox-list-with-group navbox-list navbox-odd hlist" style="width:100%;padding:0;line-height:1.4em; padding:0.33em 0;"><div style="padding:0 0.25em">

<ul><li><a href="Linear_programming" title="Linear programming"> Linear programming (LP)</a></li>

<li><a href="Quadratic_programming" title="Quadratic programming"> Quadratic programming (QP)</a></li>

<li><a href="Linear_complementarity_problem" title="Linear complementarity problem"> Linear complementarity problem (LCP)</a></li>

<li><a href="Mixed_linear_complementarity_problem" title="Mixed linear complementarity problem"> Mixed linear (MLCP)</a></li>

<li><a href="Mixed_complementarity_problem" title="Mixed complementarity problem"> Mixed (MCP)</a></li>

<li><a href="Nonlinear_complementarity_problem" title="Nonlinear complementarity problem"> Nonlinear (NCP)</a></li></ul>

</div></td></tr><tr><th scope="row" class="navbox-group" style="width:1%"><a href="Matroid" title="Matroid">Basis</a>-<a href="Exchange_algorithm" class="mw-redirect" title="Exchange algorithm">exchange algorithms</a></th><td class="navbox-list-with-group navbox-list navbox-even hlist" style="width:100%;padding:0;line-height:1.4em; padding:0.33em 0;"><div style="padding:0 0.25em">

<ul><li><a href="Simplex_algorithm" title="Simplex algorithm">Simplex</a> (<a href="George_Dantzig" title="George Dantzig">Dantzig</a>)</li>

<li><a href="Revised_simplex_algorithm" class="mw-redirect" title="Revised simplex algorithm">Revised simplex</a></li>

<li><a href="Criss-cross_algorithm" title="Criss-cross algorithm">Criss-cross</a></li>

<li><a href="Lemke's_algorithm" title="Lemke's algorithm">Lemke</a></li></ul>

</div></td></tr></tbody></table></div></div><div><div class="zim-footer">

This article is issued from <a class="external text" title="Last edited on 2025-02-11" href="https://en.wikipedia.org/wiki/?title=Revised_simplex_method&oldid=1275137996">Wikipedia</a>. The text is available under <a class="external text" href="https://creativecommons.org/licenses/by-sa/4.0/deed.en">Creative Commons Attribution-Share Alike 4.0</a> unless otherwise noted. Additional terms may apply for the media files.

</div>

</div></div>

</div>

</main>

</div>

</body></html>